"""
编辑距离(levenshtein distance)是针对二个字符串（例如英文字）
的差异程度的量化量测，量测方式是看至少需要多少次的处理
才能将一个字符串变成另一个字符串。
允许的处理有不操作、替换操作、插入操作、删除操作。
根据利文斯顿算法原理，
编写利文斯顿函数实现比较两个字符串的编辑距离。
"""


def edit_distance(string1, string2):
    rows = len(string1) + 1
    cols = len(string2) + 1
    matrix = []
    for i in range(rows):
        matrix.append([0] * cols)
    for i in range(cols):
        matrix[0][i] = i
    for i in range(rows):
        matrix[i][0] = i
    for i in range(1, rows):
        for j in range(1, cols):
            left = matrix[i - 1][j]
            up = matrix[i][j - 1]
            corner = matrix[i - 1][j - 1]
            matrix[i][j] = min([left, up, corner])
            if string1[i - 1] != string2[j - 1]:
                matrix[i][j] += 1
    return matrix[-1][-1]
